package main

import (
	"fmt"
	//"fmt"
	"math/rand"
	"time"
)

func main() {
	//fmt.Println(randLevel())
	obj := Constructor()
	target := 1
	param_1 := obj.Search(target)
	fmt.Println(param_1)
	num := 3
	obj.Add(num)
	param_3 := obj.Erase(3)
	fmt.Println(param_3)
}

type Skiplist struct {
	Head  *Node
	Level int
}

type Node struct {
	Key     int
	Forword []*Node
}

const p = 0.5
const MaxLevel = 32

func Constructor() Skiplist {
	level := randLevel()
	return Skiplist{Head: &Node{Forword: make([]*Node, MaxLevel)}, Level: level}
}

func randLevel() int {
	level := 1
	rand.Seed(time.Now().UnixNano())
	for rand.Float64() < p && level < MaxLevel {
		level++
	}
	return level
}

func (this *Skiplist) Search(target int) bool {
	x := this.Head
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forword[i] != nil && x.Forword[i].Key < target {
			x = x.Forword[i]
		}
	}

	x = x.Forword[0]
	if x != nil && x.Key == target {
		return true
	} else {
		return false
	}
}

func (this *Skiplist) Add(num int) {
	x := this.Head
	update := make([]*Node, MaxLevel)
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forword[i] != nil && x.Forword[i].Key < num {
			x = x.Forword[i]
		}
		update[i] = x
	}

	x = x.Forword[0]
	if x != nil && x.Key == num {
		return
	}

	level := randLevel()
	node := &Node{Key: num, Forword: make([]*Node, level)}

	if level > this.Level {
		for i := this.Level; i < level; i++ {
			update[i] = this.Head
		}
		this.Level = level
	}

	for i := level - 1; i >= 0; i-- {
		node.Forword[i] = update[i].Forword[i]
		update[i].Forword[i] = node
	}

	return
}

func (this *Skiplist) Erase(num int) bool {
	x := this.Head
	flag := false
	for i := this.Level - 1; i >= 0; i-- {
		for x.Forword[i] != nil {
			if x.Forword[i].Key == num {
				tmp := x.Forword[i]
				x.Forword[i] = tmp.Forword[i]
				tmp.Forword[i] = nil
				flag = true
			} else if x.Forword[i].Key < num {
				x = x.Forword[i]
			} else {
				break
			}
		}
	}
	return flag
}
